#include<vector>
#include<deque>
#include<unordered_map>
using namespace std;
class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        vector<int>res;
        if (n == 1) {
            res.push_back(0);
            return res;
        }
        if (edges.size() < 1) return res;
        unordered_map<int, vector<int>>hashMap;
        vector<int>degree(n,0);
        deque<int> queue;
        for (int i = 0; i < edges.size(); ++i) {
            hashMap[edges[i][0]].push_back(edges[i][1]);
            hashMap[edges[i][1]].push_back(edges[i][0]);
            ++degree[edges[i][0]];
            ++degree[edges[i][1]];
        }
        for (int i = 0; i < n; ++i) {
            if (degree[i] == 1)
                queue.push_back(i);
        }
        while (!queue.empty()) {
            int size = queue.size();
            res.clear();
            for (int i = 0; i < size; ++i) {
                int index = queue.front();
                res.push_back(index);
                queue.pop_front();
                for (auto it : hashMap[index]) {
                    --degree[it];
                    if (degree[it] == 1)
                        queue.push_back(it);
                }
            }
        }
        return res;
    }
};